package medium;

import data.ListNode;

import java.util.List;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/12/30 20:17
 */
public class No61_旋转链表 {
    public static void main(String[] args) {
        Solution61 solution61 = new Solution61();
        ListNode head = new ListNode(1);
        head.add(2);
        head.add(3);
        head.add(4);
        head.add(5);
        
        ListNode res = solution61.rotateRight(null, 1);
        System.out.println(res);
    }
}

class Solution61 {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        
        //形成环,切割
        //首先,把链表搞成环
        ListNode teamLeader = new ListNode(-1);
        teamLeader.next = head;
        
        //最后一个元素
        ListNode last = teamLeader;
        int kLength = 0;

        while (last != null && last.next != null) {
            last = last.next;
            kLength++;
        }
        last.next = teamLeader.next;
        //此时链表已经成环
        
        //获取切割线段 
        //初始化红绿指针用于切割位置确定
        ListNode red = teamLeader;
        ListNode green = teamLeader.next;
        //移动几次?? 

        //搜刮出来的规律
        int move = kLength - k % kLength;
        while (move != 0) {
            red = red.next;
            green = green.next;
            move--;
        }
        
        //开始切割
        red.next = null;
        return green;
    }
    
}



    //public ListNode rotateRight(ListNode head, int k) {
    //    if (head == null) {
    //        return head;
    //    }
    //    //逐步操作,逐个旋转
    //    ListNode teamLeader = new ListNode(-1);
    //    teamLeader.next = head;
    //    ListNode red = teamLeader;
    //    ListNode green = teamLeader.next;
    //    int klength = 1;
    //    //如果是false,说明k不能计算
    //    boolean kOpen = true;
    //
    //    while (k != 0) {
    //        red = teamLeader;
    //        green = teamLeader.next;
    //        //k次循环
    //        //获取green最后一个位置对应的green,red
    //        while (green != null && green.next != null) {
    //            red = red.next;
    //            green = green.next;
    //            klength++;
    //        }
    //
    //        //获取缩k,对于k过大使用
    //        //注意,计算k只计算一次,同时如果k操作完=0,则无循环
    //        if (kOpen) {
    //            if (k >= klength) {
    //                k = k % klength;
    //                if (k == 0) {
    //                    break;
    //                }
    //            }
    //            kOpen = false;
    //        }
    //
    //        //开始一波风骚操作,k一次
    //        green.next = teamLeader.next;
    //        teamLeader.next = green;
    //        red.next = null;
    //        k--;
    //    }
    //    return teamLeader.next;
    //}



